// Copyright (c) 2005-2008, Simon Howard
// Permission to use, copy, modify, and/or distribute this software
// for any purpose with or without fee is hereby granted, provided
// that the above copyright notice and this permission notice appear
// in all copies.
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
// WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
// AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
// CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
// NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

use std::cmp::Ordering;
use std::fmt::Debug;

/// A singly-linked list entry.
#[derive(Debug)]
pub struct SListEntry<T> {
    data: T,
    next: Option<Box<SListEntry<T>>>,
}

/// A singly-linked list.
#[derive(Debug)]
pub struct SList<T> {
    head: Option<Box<SListEntry<T>>>,
}

impl<T> SList<T> {
    /// Creates a new, empty singly-linked list.
    pub fn new() -> Self {
        SList { head: None }
    }

    /// Prepends a new entry to the beginning of the list.
    pub fn prepend(&mut self, data: T) {
        let new_entry = Box::new(SListEntry {
            data,
            next: self.head.take(),
        });
        self.head = Some(new_entry);
    }

    /// Appends a new entry to the end of the list.
    pub fn append(&mut self, data: T) {
        let new_entry = Box::new(SListEntry { data, next: None });
        if let Some(ref mut head) = self.head {
            let mut current = head;
            while let Some(ref mut next) = current.next {
                current = next;
            }
            current.next = Some(new_entry);
        } else {
            self.head = Some(new_entry);
        }
    }

    /// Returns the length of the list.
    pub fn length(&self) -> usize {
        let mut count = 0;
        let mut current = &self.head;
        while let Some(ref entry) = current {
            count += 1;
            current = &entry.next;
        }
        count
    }

    /// Converts the list into a vector.
    pub fn to_vec(&self) -> Vec<&T> {
        let mut vec = Vec::new();
        let mut current = &self.head;
        while let Some(ref entry) = current {
            vec.push(&entry.data);
            current = &entry.next;
        }
        vec
    }

    /// Removes the first entry that matches the given data.
    pub fn remove_data<F>(&mut self, callback: F, data: &T) -> bool
    where
        F: Fn(&T, &T) -> bool,
    {
        let mut current = &mut self.head;
        while let Some(ref mut entry) = current {
            if callback(&entry.data, data) {
                let next = entry.next.take();
                *current = next;
                return true;
            }
            current = &mut entry.next;
        }
        false
    }

    /// Sorts the list using the given comparison function.
    pub fn sort<F>(&mut self, compare_func: F)
    where
        F: Fn(&T, &T) -> Ordering,
    {
        let mut vec = self.to_vec();
        vec.sort_by(|a, b| compare_func(a, b));
        self.head = None;
        for data in vec {
            self.append(data.clone());
        }
    }

    /// Finds the first entry that matches the given data.
    pub fn find_data<F>(&self, callback: F, data: &T) -> Option<&SListEntry<T>>
    where
        F: Fn(&T, &T) -> bool,
    {
        let mut current = &self.head;
        while let Some(ref entry) = current {
            if callback(&entry.data, data) {
                return Some(entry);
            }
            current = &entry.next;
        }
        None
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_prepend() {
        let mut list = SList::new();
        list.prepend(1);
        list.prepend(2);
        assert_eq!(list.length(), 2);
        assert_eq!(list.to_vec(), vec![&2, &1]);
    }

    #[test]
    fn test_append() {
        let mut list = SList::new();
        list.append(1);
        list.append(2);
        assert_eq!(list.length(), 2);
        assert_eq!(list.to_vec(), vec![&1, &2]);
    }

    #[test]
    fn test_remove_data() {
        let mut list = SList::new();
        list.append(1);
        list.append(2);
        list.append(3);
        assert!(list.remove_data(|a, b| a == b, &2));
        assert_eq!(list.length(), 2);
        assert_eq!(list.to_vec(), vec![&1, &3]);
    }

    #[test]
    fn test_sort() {
        let mut list = SList::new();
        list.append(3);
        list.append(1);
        list.append(2);
        list.sort(|a, b| a.cmp(b));
        assert_eq!(list.to_vec(), vec![&1, &2, &3]);
    }

    #[test]
    fn test_find_data() {
        let mut list = SList::new();
        list.append(1);
        list.append(2);
        list.append(3);
        let entry = list.find_data(|a, b| a == b, &2);
        assert_eq!(entry.unwrap().data, 2);
    }
}
